package org.example.struct.array2;

/**
 * @author liyishan
 * @date 2023/10/26 10:14
 * @apiNote
 */

public class Test00918MaxSubarraySumCircular {


    public static int test(int[] nums) {
        int total = 0;
        int maxSum = nums[0];
        int curMax = 0;
        int minSum = nums[0];
        int curMin = 0;
        for(int num:nums){
            curMax = Math.max(curMax+num,num);
            maxSum = Math.max(maxSum,curMax);
            curMin = Math.min(curMin+num,num);
            minSum = Math.min(minSum,curMin);
            total += num;
        }
        return maxSum>0?Math.max(maxSum,total-minSum):maxSum;
    }

    public static int test1(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n];
        leftMax[0] = nums[0];
        int leftSum = nums[0];
        int pre = nums[0];
        int res = nums[0];
        for(int i=1;i<n;i++){
            pre = Math.max(pre+nums[i],nums[i]);
            res = Math.max(res,pre);
            leftSum += nums[i];
            leftMax[i] = Math.max(leftMax[i-1],leftSum);
        }
        int rightSum = 0;
        for(int i=n-1;i>0;i--){
            rightSum+=nums[i];
            res = Math.max(res,leftMax[i-1]+rightSum);
        }
        return res;
    }
}
